import sun.nio.ch.DirectBuffer;

import java.util.*;

/**
 * @Author: Liu, Yunfeng
 * @DateTime: 2021/7/13 21:57
 * @Description: TODO
 */
public class getSkyline {
    public static List<List<Integer>> getSkyline(int[][] buildings) {
        List<List<Integer>> result = new ArrayList<>();
        Map<Integer, Integer> map = new LinkedHashMap<>();
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        if(buildings[0][0]>=0){
            map.put(0,0);
            map.put(Integer.MAX_VALUE,0);
            stack1.push(0);
            stack1.push(Integer.MAX_VALUE);
        }
        for(int i = 0; i < buildings.length; i++){
            int peek=stack1.peek();
            while (buildings[i][0]<peek){
                peek = stack1.pop();
                stack2.push(peek);
            }
            stack1.push(peek);
            stack2.pop();
            peek = stack2.peek();
            if(buildings[i][0]!=0) {
                stack1.push(buildings[i][0]);
                if(stack1.peek() != buildings[i][0]){
                    map.put(buildings[i][0], map.get(peek));
                }else{
                    map.put(buildings[i][0], buildings[i][2]);
                }
            }else{
                map.replace(0,buildings[i][2]);
            }
            peek = stack2.pop();
            while(peek<buildings[i][1]){
                stack1.push(peek);
                int value = map.get(peek);
                map.replace(peek,Math.max(value, buildings[i][2]));
                peek = stack2.pop();
            }
            stack1.push(buildings[i][1]);
            stack1.push(peek);
            map.put(buildings[i][1],Math.max(buildings[i][2],map.get(peek)));
            while(!stack2.empty()){
                stack1.push(stack2.pop());
            }
        }
        while(!stack1.empty()){
            stack2.push(stack1.pop());
        }
        while(!stack2.empty()){
            List<Integer> list = new ArrayList<>();
            int peek =0,value =0 ;
            value = map.get(stack2.peek());
            int pre = 0;
            while(!stack2.empty()){
                pre = stack2.pop();
                if(value == map.get(pre)){
                    peek = pre;
                }else{
                    stack2.push(pre);
                    break;
                }
            }
            list.add(peek);
            list.add(map.get(pre));;
            result.add(list);
        }
        result.remove(result.size()-1);
        return result;
    }

    public static void main(String[] args) {
        int[][] buildings = {{0,2,3},{2,5,3}};
        List<List<Integer>> skyline = getSkyline(buildings);
        for(List<Integer> list : skyline){
            for(Integer i:list){
                System.out.print(i+" ");
            }
            System.out.println("");
        }
    }
}
